package com.datastructure.array;

/**
 * @author: 临晖
 * @date: 2023/10/05
 * @description:
 */


import com.datastructure.binarytree.TreeNode;
import sun.rmi.runtime.Log;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 二分法应用
 */
public class Solution01 {


    /**
     * 数组是存放在连续内存空间上的相同类型数据的集合。
     * 二分查找法：
     * 条件：
     * 1.数组是有序的
     * 总结：左闭右开，左开右闭，左闭右闭
     * 1.取值全部闭合时，用 <= ，否则用 <
     * 2.左边闭合 left = middle + 1，右边闭合 right = middle - 1，不闭合就是left = middle，right = middle;
     * 3.middle = left + ((right - left)  >> 1)，防止溢出，左开右闭 middle = left + ((right - left)  >> 1) + 1（防止-1与0）
     *
     * @param nums
     * @param target
     * @return 返回下标，否则返回-1
     */
    public static int search(int[] nums, int target) {


        if (nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }

        //定义数组和目标数
        //int[] nums = {-1, 0, 3, 5, 9, 12};
        //int target = 2;
        //定义最左下标和最有下标
        int left = 0;
        int right = nums.length - 1;

        //判断条件：左边下标必须小于等于右边下标
        while (left <= right) {
            //int index = (left + right) / 2;
            int index = left + ((right - left) >> 1);           // 防止溢出 等同于(left + right)/2
            if (nums[index] == target) {

                return index;
            } else if (nums[index] < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
        //输出下标
        return -1;
    }


    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * <p>
     * 条件：
     * 1.数组是有序的
     * 2.数组不能有重复的元素
     * <p>
     * 总结：
     *
     * @param nums
     * @param target
     * @return 找到返回下标，否则返回其要插入的下标位置
     */
    public static int searchInsert(int[] nums, int target) {
        ////在起始位置
        //if (target < nums[0]) {
        //    return 0;
        //}
        ////在结束位置
        //if (target > nums[nums.length - 1]) {
        //    return nums.length;
        //}

        //在中间位置
        int middle = -1;
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {     //左闭右闭取等于
            middle = left + ((right - left) >> 1);      //防止溢出，注意：如果这里是左开，需要middle + 1；

            if (target < nums[middle]) {
                right = middle - 1;         //如果右边是开，则不需要减一；
            } else if (target > nums[middle]) {
                left = middle + 1;
            } else {
                //有该值
                return middle;
            }
        }

        System.out.println("左边" + left);
        System.out.println("右边" + right);
        System.out.println("中间" + middle);

        //无该值
        return right + 1;       //这里是否加一也取决于右边是否闭合
    }


    /**
     * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     * 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchRange(int[] nums, int target) {
        //自己的方案
        //boolean flag = false;
        //int index1 = -1;
        //int index2 = -1;
        //for (int i = 0; i < nums.length; i++) {
        //    if (nums[i] == target) {
        //        flag = true;
        //        index1 = i;
        //        break;
        //    }
        //}
        //
        //if (flag) {
        //    for (int i = nums.length - 1; i >= index1; i--) {
        //        if (nums[i] == target) {
        //            index2 = i;
        //            break;
        //        }
        //    }
        //    return new int[]{index1, index2};
        //} else {
        //    return new int[]{index1, index2};
        //}

        //三种情况
        int leftBorder = Utils.getLeftBorder(nums, target);
        int rightBorder = Utils.getRightBorder(nums, target);

        //要找的数在俩头
        if (leftBorder == -2 || rightBorder == -2) {
            return new int[]{-1, -1};
        }
        //要找的数的中间
        else if (leftBorder >= rightBorder) {
            return new int[]{-1, -1};
        }
        //要找的数在中间（数组有值）
        else {
            return new int[]{leftBorder, rightBorder};
        }

    }


    /**
     * x的平方根
     *
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = -1;

        while (left <= right) {
            int middle = left + ((right - left) >> 1);

            if ((long) middle * middle <= x) {
                ans = middle;
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }

        return ans;
    }


    /**
     * 给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false ，
     * 完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
     * 不能使用任何内置的库函数，如  sqrt 。
     *
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        int left = 0;
        int right = num;
        int ans = -1;

        while (left <= right) {
            int middle = left + ((right - left) >> 1);
            long oldNum = (long) middle * middle;
            if (oldNum == num) {
                return true;
            } else if (num > oldNum) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return false;
    }







    public static void main(String[] args) {
        //int[] nums = {5,7,7,8,8,10};
        //int target = 8;
        //int[] length = searchRange(nums, target);
        //System.out.println(length[0] + "      " + length[1]);
    }


}




